home *** CD-ROM | disk | FTP | other *** search
/ Deutsche Edition 1 / Deutsche Edition 1.iso / amok / amok_lha / amok22.lha / CrossRef / Cross.dok < prev    next >
Text File  |  1993-08-15  |  8KB  |  237 lines
  1.                         CrossReference - Lister
  2.                      =============================
  3.  
  4.  
  5.                              Version 1.00
  6.                         geschrieben von Andreas Pahl
  7.                               13.07.1989
  8.  
  9.  
  10. Kopierrecht
  11. ------------
  12.  
  13. Das komplette Packet (Quelltext, Dokumentation und Objectcode) ist
  14. Public Domain Software. Es darf beliebig kopiert und verbreitet werden
  15. solange...
  16.  
  17. * mein Name und dieser Kopierrechtshinweis erhalten bleiben,
  18. * die Vollständigkeit des ganzen Packets gewährleistet ist, und
  19. * mit dem Vertrieb dieser Software kein Gewinn erwirtschaftet wird.
  20.  
  21. Die Kommerzielle Nutzung ohne meine ausdrückliche schriftliche
  22. Genehmigung ist untersagt. Falls Sie dies beabsichtigen, nehmen Sie
  23. bitte unter unten genannter Adresse Kontakt mit mir auf.
  24.  
  25.  
  26.  
  27. Einleitung :
  28. ------------
  29.  
  30. Ein CrossReference-Lister durchsucht den Sourcecode nach allen
  31. Bezeichnern, zählt ihr Vorkommen und gibt alle Zeilennummern aus,
  32. in denen die Bezeichner verwendet werden.
  33.  
  34.  
  35. Programm :
  36. ----------
  37.  
  38. Das Programm läßt sich zur Zeit eigentlich nur sinnvoll in Verbindung
  39. mit Modlist (eventuell werde ich in Zukunft daran koppeln) oder mit
  40. einem Editor, bei dem es eine Statuszeile gibt, in der die aktuelle
  41. Zeilennummer steht (z.B. DME), verwenden. Aber ich habe noch eine
  42. ganze Menge Ideen, das Programm wird also sicherlich noch weiterentwickelt.
  43.  
  44. Die grundlegende Datenstruktur des Programms ist ein sogenannter Trie.
  45. Ein Trie ist ein Vielwegbaum, in dessen Knoten einzelne Buchstaben eines
  46. Wortes gespeichert sind. Folgt man von der Wurzel des Trie allen möglichen
  47. Pfaden bis zu seiner Wortendmarke, erhält man alle im Trie gespeicherten
  48. Worte. Ein Beispieltrie, gebildet aus den Worten BALL, BAR, BAU, BAUM,
  49. BIER, BILD, IOD :
  50.  
  51.  
  52.  
  53.                                   Wurzel
  54.                            ______/      \__
  55.                      _____/                \__
  56.                     B                         I
  57.                  __/ \__                      |
  58.               __/       \__                   |
  59.              A             I                  O
  60.             /|\           / \                 |
  61.            / | \         /   \                |
  62.           L *R  U       E     L              *D
  63.           |     |       |     |
  64.           |     |       |     |
  65.          *L    *M      *R    *D                    * ist die Wortendmarke
  66.  
  67.  
  68. Diese Datenstruktur eignet sich besonders gut, um eingelesene Wörter
  69. alphabetisch zu speichern. Würde man die oben gezeigte Struktur so in
  70. Modula implementieren, würde das allerdings eine enorme Speicherplatz-
  71. verschwendung bedeuten, da man zu jedem Knoten 52 Nachfolger definieren
  72. müßte (je 26 Groß- und Kleinbuchstaben unter Vernachlässigung der Umlaute),
  73. von denen jedoch nie alle gebraucht werden. Deshalb führt man eine
  74. Modifikation ein und definiert einfach für jeden Knoten einen horizontalen
  75. und einen vertikalen Nachfolgerknoten. Jetzt werden nur Knoten generiert,
  76. die auch wirklich benutzt werden.
  77.  
  78.  
  79.  
  80.  
  81.                                   Wurzel
  82.                            ______/
  83.                      _____/
  84.                     B------------------------>I
  85.                  __/                          |
  86.               __/                             |
  87.              A------------>I                  O
  88.             /             /                   |
  89.            /             /                    |
  90.           L-->*R-->U    E---->L              *D
  91.           |        |    |     |
  92.           |        |    |     |
  93.          *L       *M   *R    *D                    * ist die Wortendmarke
  94.  
  95.  
  96. Dazu gehört folgende Deklaration:
  97.  
  98.  
  99.    Trie = POINTER TO Node;
  100.    Node = RECORD
  101.             Buchstabe   : CHAR;
  102.             Anzahl      : CARDINAL;         (* Häufigkeit des Bezeichners *)
  103.             Wortende    : BOOLEAN;          (* Markiert Wortende im Trie  *)
  104.             horizontal,
  105.             vertikal    : Trie;
  106.           END;
  107.  
  108.  
  109. Beim Trie wird der zu analysierende Text nun Zeichen für Zeichen eingelesen
  110. und direkt ohne Zwischenspeicherung im Trie gespeichert. Die zentrale
  111. Prozedur, die das bewirkt, ist die Prozedur INSERT. Jedesmal, wenn der
  112. erste Buchstabe eines Wortes eingelesen wurde, wird INSERT aufgerufen und zu
  113. dem Trieknoten verzweigt, der diesem ersten Buchstaben entspricht. Dann
  114. erst wird der nächste Buchstabe gelesen und derjenige Nachfolgerknoten
  115. gesucht, der diesem Buchstaben entspricht. Falls kein solcher Nachfolger
  116. existiert, wird ein neuer Knoten geschaffen. Dieses Verfahren wird solange
  117. weitergeführt, bis der letzte Buchstabe des Wortes gelesen und das Wort
  118. somit an der richtigen Stelle im Wörterbuch eingetragen ist.
  119.  
  120.  
  121. Pseudocode von INSERT:
  122. ----------------------
  123.  
  124. (* Beim ersten Aufruf sei der erste Buchstabe des Wortes bereits gelesen.
  125.  
  126.    Das gerade aktuell gelesene Zeichen sei ZEICHEN. TRIE ist gemäß obiger
  127.    Deklaration vereinbart.                                                 *)
  128.  
  129. Prozedur Insert(VAR KNOTEN:TRIE);
  130. BEGIN
  131.  
  132. Falls KNOTEN auf NIL zeigt,
  133.    dann alloziere Speicherplatz für einen neuen Knoten,
  134.    speichere darin ZEICHEN und laß KNOTEN auf diesen neuen Knoten zeigen.
  135.       Wandern: Lies das nächste Zeichen ZEICHEN.
  136.                Falls es sich bei ZEICHEN um einen Buchstaben handelt,
  137.                   dann plaziere ihn am richtigen Ort im TRIE durch
  138.                   Aufruf von Insert(KNOTEN^.vertikal),
  139.                   sonst KNOTEN^.Wortende := TRUE
  140.  
  141. Falls KNOTEN nicht auf NIL zeigt, sondern auf einen Knoten mit einem
  142. Buchstaben, der alphabetisch nach ZEICHEN kommt,
  143.    dann füge ZEICHEN vor diesem Knoten in den TRIE ein,
  144.    indem du einen neuen Knoten bildest, darin ZEICHEN speicherst und den
  145.    Horizontalzeiger dieses neuen Knotens auf den gleichen Ort richtest, auf
  146.    den KNOTEN zeigt. Anschließend soll KNOTEN neu auf den neuen Knoten
  147.    zeigen.
  148.    Führe die gleichen Aktionen aus, wie unter Wandern beschrieben.
  149.  
  150. Falls KNOTEN nicht auf NIL zeigt, sondern auf einen Knoten mit einem
  151. Buchstaben, der alphabetisch vor ZEICHEN kommt,
  152.    dann füge ZEICHEN nach diesem KNOTEN in den TRIE ein durch
  153.    Aufruf Insert(KNOTEN^.horizontal).
  154.  
  155. Falls KNOTEN nicht auf NIL zeigt, sondern auf einen Knoten mit denselben
  156. Buchstaben wie ZEICHEN,
  157.    dann führe die Aktion durch, die unter Wandern beschrieben sind.
  158. END Insert;
  159.  
  160.  
  161. Aufruf des Programms
  162. --------------------
  163.  
  164. Das Programm fragt nach derSourcedatei und nach der Ausgabedatei. Die
  165. Sourcedatei kann gleich als Parameter beim Start vom CLI aus mit übergeben
  166. werden.
  167.  
  168.  
  169. Bedeutung der Buchstaben in der Spalte Typ:
  170. -------------------------------------------
  171.  
  172.  
  173.             M = Modul
  174.             F = Importiertes Modul
  175.             I = Importierter Bezeichner
  176.             P = Prozedur
  177.             C = Konstante
  178.             T = Typ
  179.             V = Variable
  180.             B = implizit importierter Bezeichner
  181.                 (z.B. beim Importiern von Records oder Mengen. Dabei
  182.                  erscheint nur der Name des Records bzw. der Menge in der
  183.                  Import-Liste, aber nicht alle Elemente, die ja auch vom
  184.                  Programm benutzt werden können)
  185.  
  186.  
  187. Mögliche Erweiterungen:
  188. -----------------------
  189.  
  190.     - Zeilenbreite entsprechend Ausgabegerät
  191.     - Anzeigen, wo der Bezeichner definiert ist (Welches Modul, welche
  192.       Prozedur)
  193.     - Was das Programm alles anzeigen soll, irgendwie vom Benutzer wählen
  194.       lassen
  195.       (aber mit Voreinstellung)
  196.     - Mit Modlist verbinden
  197.     - Schachtelungstiefe ausgeben
  198.     - Smart-Linker auf Sourceebene
  199.     - Zu jeder Prozedur alle Bezeichner herausschreiben, die in ihr
  200.       verwendet, aber nicht deklariert werden. Hilfreich für Programm-
  201.       modifikationen und gegen unerwünschte Seiteneffekte
  202.  
  203.  
  204.  
  205.  
  206.  
  207. Falls jemand Fehler findet, so möge er sie mir doch bitte mitteilen. Auch
  208. Verbesserungswünsche sind jederzeit willkommen.
  209.  
  210.  
  211.  
  212. Viel Spaß, Andreas
  213.  
  214.  
  215.  
  216.  
  217. Adresse:
  218. ---------
  219.  
  220. Andreas Pahl
  221. Zikadenweg 22
  222. D-1000 Berlin 19
  223.  
  224. Tel. 030/302 55 37
  225.  
  226.  
  227. EMail-Adressen:
  228. ---------------
  229.  
  230. UUCP:         Domain :  macbeth@netmbx.UUCP
  231.               Bang   :  ...{pyramid|altger|tub|unido}!tmpmbx!netmbx!macbeth
  232.  
  233.  
  234. FidoNet:      2:242/1000    TO:Andreas Pahl
  235.               2:242/9000.43 TO:Andreas Pahl
  236.  
  237.